import java.util.HashMap;

public class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        int len = arr.length;

        //以i、j为结尾的最长序列的长度
        int[][] dp = new int[len][len];

        //key为arr中的元素，value为key对应的下标
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < len; i++) {
            map.put(arr[i], i);
        }

        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                int a = arr[j] - arr[i];
                int index = map.getOrDefault(a, -1);
                if (index >= 0) {
                    if (a < arr[i]) {
                        dp[i][j] = Math.max(dp[index][i] + 1, dp[i][j]);
                    }
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                ret = Math.max(ret, dp[i][j]);
            }
        }

        return ret < 1 ? 0 : ret + 2;
    }
}
